//
//  Problem67.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/11.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 67. 二进制求和
 给你两个二进制字符串，返回它们的和（用二进制表示）。
 输入为 非空 字符串且只包含数字 1 和 0。

 示例 1:
     输入: a = "11", b = "1"
     输出: "100"
 示例 2:
     输入: a = "1010", b = "1011"
     输出: "10101"
 提示：
     每个字符串仅由字符 '0' 或 '1' 组成。
     1 <= a.length, b.length <= 10^4
     字符串如果不是 "0" ，就都不含前导零。
 */
@objcMembers class Problem67: NSObject {
    func solution() {
        print(addBinaryClear("11", "0"))
        print(addBinaryClear("11", "1"))
        print(addBinaryClear("1010", "1011"))
        print(addBinaryClear("1000", "1001"))
    }
    
    func addBinary(_ a: String, _ b: String) -> String {
        let A = Array(a)
        let B = Array(b)
        
        var i = A.count - 1
        var j = B.count - 1
        
        var reslut: String = ""
        var n = 0
        while i >= 0 || j >= 0 {
            if i >= 0, j >= 0 {
                if A[i] == "1", B[j] == "1" {
                    reslut.insert(n == 0 ? "0" : "1", at: reslut.startIndex)
                    n = 1
                } else if A[i] == "1" || B[j] == "1" {
                    reslut.insert(n == 0 ? "1" : "0", at: reslut.startIndex)
                    n = n == 0 ? 0 : 1
                } else {
                    reslut.insert(n == 0 ? "0" : "1", at: reslut.startIndex)
                    n = 0
                }
                i -= 1
                j -= 1
            } else if i >= 0 {
                if A[i] == "1" {
                    reslut.insert(n == 0 ? "1" : "0", at: reslut.startIndex)
                    n = n == 0 ? 0 : 1
                } else {
                    reslut.insert(n == 0 ? "0" : "1", at: reslut.startIndex)
                    n = 0
                }
                i -= 1
            } else if j >= 0 {
                if B[j] == "1" {
                    reslut.insert(n == 0 ? "1" : "0", at: reslut.startIndex)
                    n = n == 0 ? 0 : 1
                } else {
                    reslut.insert(n == 0 ? "0" : "1", at: reslut.startIndex)
                    n = 0
                }
                j -= 1
            }
        }
        if n == 1 {
            reslut.insert("1", at: reslut.startIndex)
        }
       
        return String(reslut)
    }
    
    func addBinaryClear(_ a: String, _ b: String) -> String {
        let A = Array(a)
        let B = Array(b)
        
        var i = A.count - 1
        var j = B.count - 1
        
        var reslut: String = ""
        var n = 0
        while i >= 0 || j >= 0 {
            n += i >= 0 ? (A[i] == "0" ? 0 : 1) : 0
            n += j >= 0 ? (B[j] == "0" ? 0 : 1) : 0
            reslut.insert(n % 2 == 0 ? "0" : "1", at: reslut.startIndex)
            n /= 2
            i -= 1
            j -= 1
        }
        if n == 1 {
            reslut.insert("1", at: reslut.startIndex)
        }
       
        return String(reslut)
    }
}
